<!DOCTYPE html>
<html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-0 vector-toc-not-available vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-0 skin-theme-clientpref-day vector-sticky-header-enabled" lang="de" dir="ltr"><head>
<meta charset="UTF-8">
<title>Gradfolge</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="icon" type="image/png" href="./_res_/favicon.png">
<link rel="canonical" href="https://de.wikipedia.org/wiki/Gradfolge"> <link href="./_mw_/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.wikimediamessages.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link href="./_mw_/ext.gadget.citeRef.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.defaultPlainlinks.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonHide.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonLayout.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonStyle.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiDarkmode.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiResponsive.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.specialSearch.css" rel="stylesheet" type="text/css">
<link rel="stylesheet" type="text/css" href="./_mw_/site.styles.css">
<link rel="stylesheet" type="text/css" href="./_mw_/noscript.css">
<link rel="stylesheet" type="text/css" href="./_res_/footer.css">
<link rel="stylesheet" type="text/css" href="./_res_/vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Gradfolge rootpage-Gradfolge skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Gradfolge</span></h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="contentSub">
<div id="mw-content-subtitle"></div>
</div>
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">
<p>Als <b>Gradfolge</b> (oder auch <b>Valenzsequenz</b> bzw. <b>Gradsequenz</b>) eines <a href="Einfacher_Graph" title="Einfacher Graph">einfachen Graphen</a> bezeichnet man in der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> die aufsteigende Folge der <a href="Grad_(Graphentheorie)" title="Grad (Graphentheorie)">Knotengrade</a> aller <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> eines Graphen.
</p>
<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>
<p>Die Gradfolge eines <a href="Einfacher_Graph" title="Einfacher Graph">einfachen Graphen</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=(V,E)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>G</mi>
<mo>=</mo>
<mo stretchy="false">(</mo>
<mi>V</mi>
<mo>,</mo>
<mi>E</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle G=(V,E)}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/644a8d85ee410b6159ca2bdb5dcb9097e2c8f182.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.331ex; height:2.843ex;" alt="{\displaystyle G=(V,E)}" loading="lazy"></span> mit den <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{1},v_{2},\ldots ,v_{n}\in V}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo>∈<!-- ∈ --></mo>
<mi>V</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle v_{1},v_{2},\ldots ,v_{n}\in V}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d745eb661186c53fe7bd79186a7ff9c8e6be5762.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.55ex; height:2.509ex;" alt="{\displaystyle v_{1},v_{2},\ldots ,v_{n}\in V}" loading="lazy"></span> und <a href="Grad_(Graphentheorie)" title="Grad (Graphentheorie)">Knotengraden</a>
<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d(v_{1})\leq d(v_{2})\leq \dots \leq d(v_{n})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>d</mi>
<mo stretchy="false">(</mo>
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>≤<!-- ≤ --></mo>
<mi>d</mi>
<mo stretchy="false">(</mo>
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>≤<!-- ≤ --></mo>
<mo>⋯<!-- ⋯ --></mo>
<mo>≤<!-- ≤ --></mo>
<mi>d</mi>
<mo stretchy="false">(</mo>
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle d(v_{1})\leq d(v_{2})\leq \dots \leq d(v_{n})}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/21aba073245348ed4de7a4e7c34a20aea4441fab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.804ex; height:2.843ex;" alt="{\displaystyle d(v_{1})\leq d(v_{2})\leq \dots \leq d(v_{n})}" loading="lazy"></span> ist die Folge <a href="Nat%C3%BCrliche_Zahlen" class="mw-redirect" title="Natürliche Zahlen">natürlicher Zahlen</a>
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{1},d_{2},\ldots ,d_{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>d</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>d</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<msub>
<mi>d</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle d_{1},d_{2},\ldots ,d_{n}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5929923455d26ba66ac1863d272eed73a5355ba9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.166ex; height:2.509ex;" alt="{\displaystyle d_{1},d_{2},\ldots ,d_{n}}" loading="lazy"></span>,</dd></dl>
<p>wobei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{i}=d(v_{i})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>d</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>=</mo>
<mi>d</mi>
<mo stretchy="false">(</mo>
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle d_{i}=d(v_{i})}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/30fc6009fa0df9ceaad63c5f7f36f6484587e2f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.06ex; height:2.843ex;" alt="{\displaystyle d_{i}=d(v_{i})}" loading="lazy"></span> für alle <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=1,2,\dots ,n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
<mo>,</mo>
<mn>2</mn>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle i=1,2,\dots ,n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c1d5159f58045d75d8a37feecb2bd11bcc772937.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.833ex; height:2.509ex;" alt="{\displaystyle i=1,2,\dots ,n}" loading="lazy"></span> jeweils den Grad des Knotens <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7dffe5726650f6daac54829972a94f38eb8ec127.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle v_{i}}" loading="lazy"></span> angibt. Eine aufsteigende Folge natürlicher Zahlen heißt <b>graphisch</b>, wenn mindestens ein einfacher Graph existiert, der diese Gradfolge aufweist.
</p>
<div class="mw-heading mw-heading2"><h2 id="Beispiele">Beispiele</h2></div>
<div class="mw-heading mw-heading3"><h3 id="Gradfolge">Gradfolge</h3></div>
<p>Das <a href="Haus_vom_Nikolaus" title="Haus vom Nikolaus">Haus vom Nikolaus</a> hat mit der Knotennummerierung im nebenstehenden Bild die Knotengrade <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d(1)=d(2)=3,d(3)=d(4)=4}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>d</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mi>d</mi>
<mo stretchy="false">(</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mn>3</mn>
<mo>,</mo>
<mi>d</mi>
<mo stretchy="false">(</mo>
<mn>3</mn>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mi>d</mi>
<mo stretchy="false">(</mo>
<mn>4</mn>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mn>4</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle d(1)=d(2)=3,d(3)=d(4)=4}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/21e830b04cba3561a2cb7d66e0960f561780d22c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.503ex; height:2.843ex;" alt="{\displaystyle d(1)=d(2)=3,d(3)=d(4)=4}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d(5)=2}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>d</mi>
<mo stretchy="false">(</mo>
<mn>5</mn>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mn>2</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle d(5)=2}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7d718abc798836c43d3e0a7e3cd67d1315df6ed4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.449ex; height:2.843ex;" alt="{\displaystyle d(5)=2}" loading="lazy"></span>. Eine Sortierung nach dem Grad ergibt dann die zugehörige Gradfolge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2,3,3,4,4}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>2</mn>
<mo>,</mo>
<mn>3</mn>
<mo>,</mo>
<mn>3</mn>
<mo>,</mo>
<mn>4</mn>
<mo>,</mo>
<mn>4</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2,3,3,4,4}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4f079e2395291543bc095f23a3e32234cfd05eec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.948ex; height:2.509ex;" alt="{\displaystyle 2,3,3,4,4}" loading="lazy"></span>.
</p>
<div class="mw-heading mw-heading3"><h3 id="Graphische_Folgen">Graphische Folgen</h3></div>
<p>Die Folge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0,1,2,2,3,3,3}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>0</mn>
<mo>,</mo>
<mn>1</mn>
<mo>,</mo>
<mn>2</mn>
<mo>,</mo>
<mn>2</mn>
<mo>,</mo>
<mn>3</mn>
<mo>,</mo>
<mn>3</mn>
<mo>,</mo>
<mn>3</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 0,1,2,2,3,3,3}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/37dc62dc3ff0b03adf57aa0a8a7721ea70320db2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.341ex; height:2.509ex;" alt="{\displaystyle 0,1,2,2,3,3,3}" loading="lazy"></span> ist graphisch, da der eingangs gezeigte Graph genau diese Grade hat. Die Folge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1,3,4}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>1</mn>
<mo>,</mo>
<mn>3</mn>
<mo>,</mo>
<mn>4</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 1,3,4}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7e3030bb1977e5d30326dfefd2a52f9d51772c5c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.555ex; height:2.509ex;" alt="{\displaystyle 1,3,4}" loading="lazy"></span> ist aber beispielsweise nicht graphisch, da kein einfacher Graph mit drei Ecken existieren kann, der einen Knoten mit Grad vier hat.
</p>
<div class="mw-heading mw-heading2"><h2 id="Verwendung">Verwendung</h2></div>
<p>Gradfolgen werden in der Graphentheorie beim <a href="Hamiltonkreisproblem" title="Hamiltonkreisproblem">Hamiltonkreisproblem</a> betrachtet, insbesondere bei einem Satz von <a href="Va%C5%A1ek_Chv%C3%A1tal" title="Vašek Chvátal">Vašek Chvátal</a>, der Aussagen über die Existenz von Hamiltonkreisen durch die Betrachtung von Gradfolgen folgert.
</p>
<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>
<ul><li>Reinhard Diestel: <cite style="font-style:italic">Graphentheorie</cite>. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 S.).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Gradfolge&rft.au=Reinhard+Diestel&rft.btitle=Graphentheorie&rft.date=2010&rft.genre=book&rft.isbn=9783642149115&rft.place=Berlin&rft.pub=Springer" style="display:none"> </span></li></ul></div><!--htdig_noindex--><div><div class="zim-footer">
Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-10-08" href="https://de.wikipedia.org/wiki/?title=Gradfolge&oldid=249260559">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
<script src="./_webp_/webpHandler.js"></script>
</body></html>